package org.hot100_3;


public class leetcode42 {
    public int trap(int[] height) {
        int sum = 0;
        int n = height.length;

        for (int i = 1; i < n; i++) {
            //寻找左侧最大值
            int maxLeftHeight = 0;
            for (int j = 0; j < i; j++) {
//                maxLeftHeight = Math.max(maxLeftHeight, height[j]);
                //剪枝
                if (height[j]>maxLeftHeight){
                    maxLeftHeight=height[j];
                }
            }

            //寻找右侧最大值
            int maxRightHeight = 0;
            for (int j = i + 1; j < n; j++) {
//                maxRightHeight = Math.max(maxRightHeight, height[j]);
                if (height[j]>maxRightHeight){
                    maxRightHeight=height[j];
                }
            }

            int min = Math.min(maxLeftHeight, maxRightHeight);
            if (min > height[i]) {
                sum += min - height[i];
            }
        }

        return sum;
    }
}
